//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 
//
// 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 
//
// 
//
// 示例 1: 
//
// 
//输入: [3,2,1,5,6,4] 和 k = 2
//输出: 5
// 
//
// 示例 2: 
//
// 
//输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
//输出: 4 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= nums.length <= 104 
// -104 <= nums[i] <= 104 
// 
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 
// 👍 1377 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;
import java.util.PriorityQueue;

public class KthLargestElementInAnArray {
    public static void main(String[] args) {
        Solution solution = new KthLargestElementInAnArray().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 将数组进行排序，排序之后输出对应位置就行了
         * 可以选择堆排序（java提供了一个类PriorityQueue，底层通过小顶堆来实现）
         * 快速排序（如下代码）
         * 可以直接使用Arrays.sort方法
         */
        public int findKthLargest(int[] nums, int k) {
            quickSort(nums, 0, nums.length-1);
            return nums[nums.length-k];
        }

        /**
         * 使用快速排序的方法进行排序
         */
        public void quickSort(int[] nums,int left,int right){
            int l = left;
            int r = right;
            int pivot = nums[l + (r-l)/2];//中轴直接取中间值
            int temp = 0;
            while (l<r){
                //寻找不满足顺序要求的下标
                while (nums[l]< pivot) l++;
                while (nums[r]> pivot) r--;
                if (l>=r) break;//说明都找到了中轴的位置，当前轮次不用交换了
                temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                if (nums[l] == pivot) r--;
                if (nums[r] == pivot) l++;
            }

            if (l==r){//防止死循环的发生，可以参考之前的注释
                l++;
                r--;
            }
            if (left<r) quickSort(nums, left, r);
            if (l<right) quickSort(nums, l, right);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
    /**
     * 通过java提供的PriorityQueue来实现
     * 因为底层是一个小顶堆，在添加完以一个元素之后判断堆的大小是否超过了k
     * 超过k之后就将堆顶元素进行删除，此时删除的元素是堆中最小的那个，添加完所有元素之后
     * 堆中元素个数为k，此时堆顶的元素就是原始数组中第k大的元素了
     * 比如想得到最大的元素，即k为1
     * 原始数组为1 2 3时，添加1之后不删除，添加2之后删除1，添加3之后删除2
     * 最后返回的元素即为3
     */
    public int findKthLargest2(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : nums){
            pq.add(num);
            if (pq.size()>k) pq.poll();
        }
        return pq.peek();
    }

}